import org.junit.Test;

/**
 * @作者 钟先崟
 * @时间 2023-01-28 16:24
 * @功能 37. 解数独
 * 编写一个程序，通过填充空格来解决数独问题。
 * <p>
 * 数独的解法需 遵循如下规则：
 * <p>
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：board = [{'5','3','.','.','7','.','.','.','.'},{'6','.','.','1','9','5','.','.','.'},{'.','9','8','.','.','.','.','6','.'},{'8','.','.','.','6','.','.','.','3'},{'4','.','.','8','.','3','.','.','1'},{'7','.','.','.','2','.','.','.','6'},{'.','6','.','.','.','.','2','8','.'},{'.','.','.','4','1','9','.','.','5'},{'.','.','.','.','8','.','.','7','9'}]
 * 输出：[{'5','3','4','6','7','8','9','1','2'},{'6','7','2','1','9','5','3','4','8'},{'1','9','8','3','4','2','5','6','7'},{'8','5','9','7','6','1','4','2','3'},{'4','2','6','8','5','3','7','9','1'},{'7','1','3','9','2','4','8','5','6'},{'9','6','1','5','3','7','2','8','4'},{'2','8','7','4','1','9','6','3','5'},{'3','4','5','2','8','6','1','7','9'}]
 * 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
 * <p>
 * <p>
 * <p>
 * <p>
 * 提示：
 * <p>
 * board.length == 9
 * board[i].length == 9
 * board[i][j] 是一位数字或者 '.'
 * 题目数据 保证 输入数独仅有一个解
 */
public class Solution
{
    public static void main(String[] args)
    {
//        char[][] board = new char[][]{{'5', '3', '.', '.', '7', '.', '.', '.', '.'}, {'6', '.', '.', '1', '9', '5', '.', '.', '.'}, {'.', '9', '8', '.', '.', '.', '.', '6', '.'}, {'8', '.', '.', '.', '6', '.', '.', '.', '3'}, {'4', '.', '.', '8', '.', '3', '.', '.', '1'}, {'7', '.', '.', '.', '2', '.', '.', '.', '6'}, {'.', '6', '.', '.', '.', '.', '2', '8', '.'}, {'.', '.', '.', '4', '1', '9', '.', '.', '5'}, {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
//        char[][] board = new char[][]{
//                {'.', '.', '9', '7', '4', '8', '.', '.', '.'},
//                {'7', '.', '.', '.', '.', '.', '.', '.', '.'},
//                {'.', '2', '.', '1', '.', '9', '.', '.', '.'},
//                {'.', '.', '7', '.', '.', '.', '2', '4', '.'},
//                {'.', '6', '4', '.', '1', '.', '5', '9', '.'},
//                {'.', '9', '8', '.', '.', '.', '3', '.', '.'},
//                {'.', '.', '.', '8', '.', '3', '.', '2', '.'},
//                {'.', '.', '.', '.', '.', '.', '.', '.', '6'},
//                {'.', '.', '.', '2', '7', '5', '9', '.', '.'}
//        };
        char[][] board = new char[][]{
                {'.', '.', '9', '7', '4', '8', '.', '.', '.'},
                {'7', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '2', '.', '1', '.', '9', '.', '.', '.'},
                {'.', '.', '7', '.', '.', '.', '2', '4', '.'},
                {'.', '6', '4', '.', '1', '.', '5', '9', '.'},
                {'.', '9', '8', '.', '.', '.', '3', '.', '.'},
                {'.', '.', '.', '8', '.', '3', '.', '2', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '6'},
                {'.', '.', '.', '2', '7', '5', '9', '.', '.'}
        };

        solveSudoku(board);
        System.out.println(board);
    }

    public static int row = 0;//位置行
    public static int line = 0;//位置列
    public static int resFlag = 0;

    public static void solveSudoku(char[][] board)
    {
        resFlag = 0;//力扣的判题机在读取您的代码后，对每个测试用例，都会初始化一次类，但全局变量和类内静态变量需要您手动初始化
        int numFlag = 0;
        //获取最近的空位置
        for (int i = row; i < 9; i++)
        {
            numFlag = 0;
            for (int j = 0; j < 9; j++)
            {
                if (i == row && j == 0)
                {
                    j = line;
                }
                if (board[i][j] == '.')
                {
                    numFlag = 1;
                    row = i;
                    line = j;
                    break;
                }
            }
            if (numFlag == 1) break;
        }

        if (numFlag == 0)
        {
            resFlag = 1;
            return;
        }

        //选出正确的数
        for (int num = 1; num < 10; num++)
        {
            int rowFlag = 0;
            int lineFlag = 0;
            int sudokuFlag = 0;
            //行判断
            for (int i = 0; i < 9; i++)
            {
                if (Integer.toString(num).charAt(0) == board[row][i])
                {
                    rowFlag = 1;
                    break;
                }
            }
            if (rowFlag == 1) continue;
            //列判断
            for (int j = 0; j < 9; j++)
            {
                if (Integer.toString(num).charAt(0) == board[j][line])
                {
                    lineFlag = 1;
                    break;
                }
            }
            if (lineFlag == 1) continue;
            //九宫格判断
            for (int k = 0; k < 9; k++)
            {
                int x = row - row % 3;
                int y = line - line % 3;
                int x1 = 0;
                int y1 = 0;
                switch (k)
                {
                    case 0:
                        x1 = x + 0;
                        y1 = y + 0;
                        break;
                    case 1:
                        x1 = x + 0;
                        y1 = y + 1;
                        break;
                    case 2:
                        x1 = x + 0;
                        y1 = y + 2;
                        break;
                    case 3:
                        x1 = x + 1;
                        y1 = y + 0;
                        break;
                    case 4:
                        x1 = x + 1;
                        y1 = y + 1;
                        break;
                    case 5:
                        x1 = x + 1;
                        y1 = y + 2;
                        break;
                    case 6:
                        x1 = x + 2;
                        y1 = y + 0;
                        break;
                    case 7:
                        x1 = x + 2;
                        y1 = y + 1;
                        break;
                    case 8:
                        x1 = x + 2;
                        y1 = y + 2;
                        break;
                }
                if (Integer.toString(num).charAt(0) == board[x1][y1])
                {
                    sudokuFlag = 1;
                    break;
                }
            }
            if (sudokuFlag == 0)
            {
                int oldRow = row;
                int oldLine = line;
                board[row][line] = Integer.toString(num).charAt(0);
                solveSudoku(board);
                if (resFlag == 1)
                {
                    row = 0;//力扣的判题机在读取您的代码后，对每个测试用例，都会初始化一次类，但全局变量和类内静态变量需要您手动初始化
                    line = 0;//力扣的判题机在读取您的代码后，对每个测试用例，都会初始化一次类，但全局变量和类内静态变量需要您手动初始化
                    break;
                }
                else
                {
                    row = oldRow;
                    line = oldLine;
                    board[oldRow][oldLine] = '.';
                }
            }
        }
    }
}
